package cn.suchan.jianzhi.q25_link;

import java.util.ArrayList;

/**
 * 知识点：复杂链表的复制
 * 题目描述
 * 输入一个复杂链表
 * （每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），
 * 返回结果为复制后复杂链表的head。
 * （注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
 *
 * @author suchan
 * @date 2019/05/29
 */
public class Solution {

    /**
     * 这道题就不参考别人的做法了，因为我看着别人的做法感觉更复杂更没效率，所以只列出自己写的
     *
     * @param pHead
     * @return
     */
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }
        RandomListNode nextNode = pHead;
        ArrayList<RandomListNode> nodeList = new ArrayList();
        int temp = 0;
        // 生成新的链表节点
        while (nextNode != null) {
            RandomListNode cNode = new RandomListNode(nextNode.label);
            // 先存random的引用，要不然后面不知道怎么拿到这个关系
            if (nextNode.random != null) {
                cNode.random = nextNode.random;
            }
            nodeList.add(cNode);
            // 指定next节点
            if (temp > 0) {
                nodeList.get(temp - 1).next = cNode;
            }
            nextNode = nextNode.next;
            temp++;
        }
        // 指定random节点
        for (int i = 0; i < nodeList.size(); i++) {
            for (int j = 0; j < nodeList.size(); j++) {
                if (nodeList.get(i).random != null
                        && nodeList.get(i).random.label == nodeList.get(j).label) {
                    nodeList.get(i).random = nodeList.get(j);
                }
            }
        }
        return nodeList.get(0);
    }

    public static void main(String[] args) {

        RandomListNode pHead = new RandomListNode(0);
        RandomListNode node1 = new RandomListNode(1);
        RandomListNode node2 = new RandomListNode(2);
        RandomListNode node3 = new RandomListNode(3);
        RandomListNode node4 = new RandomListNode(4);

        pHead.next = node1;
        pHead.random = node3;
        node1.next = node2;
        node1.random = pHead;
        node2.next = node3;
        node2.random = node1;
        node3.next = node4;
        node3.random = node4;

        Solution solution = new Solution();
        RandomListNode cHead = solution.Clone(pHead);
        System.out.println("pHead==>" + pHead);
        System.out.println("cHead==>" + cHead);

        RandomListNode temp = cHead;
        while (temp != null) {
            System.out.println("==========================");
            System.out.println("label==>" + temp.label);
            if (temp.next != null) {
                System.out.println("next==>" + temp.next.label);
            }
            if (temp.random != null) {
                System.out.println("random==>" + temp.random.label);
            }
            temp = temp.next;
        }


        /*
        // 这里就是测试一下list的元素为空时候调用get()方法时的情况
        ArrayList test = new ArrayList();
        test.add(0);
        test.add(1);
        test.add(2);
        test.add(null);
        try {
            System.out.println(test.size());
            if (test.get(3) == null) {
                System.out.println("空的！！");
            }
        } catch (IndexOutOfBoundsException e) {
            System.out.println("抓到了！！");
        }*/

    }
}
